1. Field of the Invention
This invention relates to an improved method for rapidly identifying a minimal subset of interconnection circuits (nets) in a multi-chip-module that must be rerouted in order to bring coupled noise on all nets within a specified limit.
2. Description of the Prior Art
State-of-the-art integrated circuit chips have a very high-level of integration, containing millions of circuits. This high-density results in a large number of terminals (I/O pins) on the chips for communication with other chips. Along with advances in chip technology, packaging technology has made similar technological strides. On a relatively small area on a multi-chip-module (MCM)--approximately 8".times.8"--it is possible to package over a hundred chips. Typical MCMs provide 50-75 wiring planes for routing the interconnections between the chips. But, despite the larger number of wiring planes, the high pin count on the chips results in a high density of wires on the planes. The close proximity of the wires in conjunction with the high speed of signals that travel on them results in many kinds of noise--coupling, reflection, cross-talk, Delta-I, etc. This invention addresses the problem of reducing coupled noise to acceptable levels. Coupled noise is the induction of signal by a signal-carrying net or nets onto nearby nets when they are quiet. The coupled noise, if large, can cause false switching of circuits. Hence, it is crucial for the correction operation of high-performance MCMs in computers to keep the noise below certain thresholds.
The known wiring programs that route the interconnection nets of the chips in MCMs, at best, can only estimate the coupled noise that would potentially exist when the connections are actually manufactured. What appears to be a good wiring route can have unacceptable noise problems in the manufactured product. In such situations, it is important to identify and reroute the noisy wires. Since the noise violators usually have strong coupling with other nets, it follows that these noise violator nets also contribute noise to other nets. When a noise violator is rerouted, the noise on one or more other noise violators is often reduced--sometimes to acceptable levels. Hence, it is usually sufficient to reroute only a subset of noise violators in order reduce the noise on all nets on the MCM to acceptable limits. Another solution to the noise problem is to rip-up the nets that contribute a high amount of noise to the coupled nets. Again, it is important to note that when a noise contributing net is ripped-up, it often reduces noise on more than one noise violators. After the subset of noise violators is identified, they can be rerouted in less congested areas, or they can be removed and routed with discrete wires, reducing the number of noise violators on the package to zero. Manufacturing and other consideration limits the number of discrete wires that can be wired on a package; therefore, it is desirable to identify the smallest subset of wires to be rewired so that the noise on the package has the largest reduction.
There is no router program that can guarantee zero noise violations. One reason is the imperfect modeling of the actual noise that can exist after the packages are manufactured. All routing programs produce less than optimal wiring. So a typical MCM package has a number of nets with noise that exceeds the specified limits for noise (i.e., noise violators). Hence, it becomes essential to identify a subset of noise-violators to be ripped-up and rerouted with tighter wiring constraints, or to be wired as discrete wires. It is estimated that a skilled designer can manually resolve up to six noise violations per day, using prior art procedures. The prior art method is mainly manual. Noisy nets are identified, which are then manually rerouted--with no knowledge of how the noise on other nets is changing. Noise is calculated at the end of rerouting phase of all nets. The calculations give a new list of noisy nets--possibly a longer list than before. Nets are again ripped-up and rerouted. This cycle of rerouting and noise calculation is carried out until there are no more noisy nets. Hence, it is advantageous to automate the process, for reasons of time and money. But, unfortunately, as mentioned below, the problem of finding the smallest such subset is not susceptible to a mathematical solution. Further, the problem has no scheme for an approximate solution.
The problem addressed by this invention can be stated as follows:
Statement 1. Given a package P with a set of noise violators N, find a subset M of N such that if the nets in M are deleted, then there are no noise violators on P. PA1 Statement 2. Given a package P, and a limit D on the number of discrete wires that can be wired on the package, and a set of noise violators N, find a subset M of N such .vertline.M.vertline..ltoreq.D and that the deletion of nets in M results in the least number of remaining violators: PA1 1. Active Net: A net carrying signal that contributes noise to neighboring nets via coupling. PA1 2. Quiet Net: A net receiving coupled noise from an active net. PA1 3. Active Noise: The total noise contributed by an active net to all noise violators. PA1 4. Quiet Noise: The total noise coupled onto a quiet net. PA1 5. Noise Violator: A net whose quiet noise exceeds the threshold noise as specified by the technology. PA1 6. Noise Contributor An active net that has a noise-coupling with another net.
Wherein the terms are defined as follows:
It can be seen that Statement 2 is a generalization of Statement 1. If D is zero and if the number of remaining violators is to be zero, then Statement 2 reduces to Statement 1. It can be shown that Statement 1 is NP-complete, meaning that there is no known deterministic way to find a solution to an instance of the problem in time that is polynomial in the size of the statement. It can be shown that the independent set problem is an instance of Statement 1. The independent set stated is NP-complete. It has been shown that there are no approximation schemes for the independent set stated, hence implying that no approximation scheme exists for solving Statement 1.